package leetbook.string;

import datastruct.tree.Trie;

import java.util.ArrayList;
import java.util.List;


public class Solution6 {

    public static void main(String[] args) {

    }

    //一个单词一个单词回溯
    public List<String> findWords1(char[][] board, String[] words) {
        ArrayList<String> total = new ArrayList<>();
        for (String word: words) {
            if(findWord(board,word)) total.add(word);
        }
        return total;
    }

    boolean findWord(char[][] board, String word){
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if(findWordStartFromIJ(board,word,i,j,0))
                    return true;
            }
        }
        return false;
    }

    boolean findWordStartFromIJ(char[][] board, String word, int i, int j, int wordi){
        if(word.charAt(wordi)!=board[i][j]) return false;
        if(++wordi==word.length()) return true;
        //设置禁忌搜索
        char tmp = board[i][j];
        board[i][j] = 0;
        //上下左右找
        int row = board.length, col = board[0].length;
        boolean flag =
                (i>0&&findWordStartFromIJ(board,word,i-1,j,wordi))||
                        (i<row-1&&findWordStartFromIJ(board,word,i+1,j,wordi))||
                        (j>0&&findWordStartFromIJ(board,word,i,j-1,wordi))||
                        (j<col-1&&findWordStartFromIJ(board,word,i,j+1,wordi));
        //搜索完毕，放开禁忌
        board[i][j] = tmp;
        return flag;
    }
}